1809D - Binary String Sorting - CodeForces Solution

// Problem: D. Binary String Sorting
// Contest: Codeforces - Educational Codeforces Round 145 (Rated for Div. 2)
// URL: https://codeforces.com/contest/1809/problem/D
// Memory Limit: 256 MB
// Time Limit: 2000 ms

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define pb push_back
#define ppb pop_back
#define sp <<" "<<
#define yes cout<<"YES"<<endl
#define no cout<<"NO"<<endl
#define min3(a, b, c) min(c, min(a, b))
#define min4(a, b, c, d) min(d, min(c, min(a, b)))
#define all(c) c.begin(), c.end()
#define INF 1e18
#define mod 1000000007
#define pi (3.141592653589)

typedef pair<ll,pair<ll,ll>>ppl;
typedef pair<ll,ll>pl; 
typedef vector<ll> vll;


const int M = 1e9+7;

void solve()
{
	string s;
	cin>>s;
	int n = s.size();
	int n1 = 0;
	ll a = 1e12, b = 1e12+1;
	vector<int>v(n);
	vector<int>v1(n);
	int temp = 0;
	for(int i = n-1;i>=0;i--){
		if(s[i] == '0'){
			temp++;
		}
		v[i] = temp;
	}
	temp = 0;
	for(int i = n-1;i>=0;i--){
		if(s[i] == '1'){
			temp++;
		}
		v1[i] = temp;
	}
	ll ans = 1e18;
	int f1 = -1;
	for(int i = 0;i<n;i++){
		if(s[i] == '1'){
			f1 = i;
			break;
		}
	}
	if(f1 == -1 || v[0]==0 || f1 == n-1){
		cout<<"0"<<endl;
		return;
	}
	ll tempans = 0;
	for(int i = f1;i<n;i++){
		if(s[i]=='0') continue;
		if(s[i+1] == '0'){
			ans = min(ans, tempans+ (a + (v[i]-1)*b));
		}else{
			ans = min(ans, tempans+ ((v[i])*b));
		}
		ans = min(ans,tempans + (v1[i]*b));
		tempans += b;
	}
	cout<<ans<<endl;
}
int main()
{
	//vvi. don't delete it
    ios_base::sync_with_stdio(false); 
    cin.tie(NULL); 
    cout.tie(NULL);
    int t = 1;
    cin>>t;
    while (t--)
    {
        solve();
    }
}